import collections
from typing import List

# 1：1. 给你一个nums，target，找到两个数加和是target，返回其index；你可以认为答案是唯一的
class TwoNumsSum(object):
    def solution(self, nums: List[int], target: int) -> List[int]:
        # 先排序：
        # 再使用双指针解法
        left=0
        right=len(nums)-1
        check=[(index,num) for index,num in enumerate(nums)]
        check=sorted(check, key=lambda x:x[1])
        while left<=right:
            sums=check[left][1]+check[right][1]
            if sums==target:
                return [check[left][0],check[right][0]]
            if sums>target:
                right-=1
            else:
                left+=1
        return [-1,-1]
    def solution_easy(self, nums: List[int], target: int) -> List[int]:
        # 直接用哈希表解决问题：
        # ⭐ 这道题很好的体现了哈希表的快速查找特征，甚至不需要回头循环，因为不存在顺序查找问题！！！
        # 时间复杂度极低！！
        hashtable=dict()
        for i,num in enumerate(nums):
            if target-num in hashtable:
                return [hashtable[target-num],i]
            hashtable[num]=i
        return [-1,-1]

    def test(self):
        nums=[5,12,4,1,9]
        target=13
        print(self.solution_easy(nums,target))

# 2：49. 字母异位词分组：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
# 字母异位词：就是使用了相同的字母拼成的单词：ate,eat,tea
class GroupAnagrams:
    def solution(self, strs: List[str]) -> List[List[str]]:
        # 这道题算是奇思妙想题吧：
        # 思路1：排序：互为异位词的单词排序后肯定是一样的：
        # 创建默认值为列表的字典:
        import collections
        mp = collections.defaultdict(list)
        for str in strs:
            keys = "".join(sorted(str))
            mp[keys].append(str)
        return list(mp.values())

    def solution2(self, strs: List[str]) -> List[List[str]]:
        # 这是有关字母的常规的解法：
        # 就是利用字母表的特性，我来进行计数：
        mp=collections.defaultdict(list)
        for st in strs:
            counts=[0]*26 # 这里对每一个单词都进行字母计数，计数列表一样的肯定是字母异位词
            for ch in st:
                counts[ord(ch)-ord("a")]+=1
                # 需要将 list 转换成 tuple 才能进行哈希,list不能作为键！！
                mp[tuple(counts)].append(st)
        return list(mp.values())

    def test(self):
        strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
        print(self.solution2(strs))

# 3. 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
# 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
# ⭐ 降低时间复杂度的一大利器：哈希表；关键是存什么？
class LongestConsecutive:
    def solution(self, nums: List[int]) -> int:
        # 如果用了内置的排序算法，时间复杂度会如何计算？
        # 还是有很多脑经急转弯的小技巧：1）用集合去重；2）遍历时先找每个x的x-1如果没有，则它是序列的起点
        nums_set=set(nums)
        longest_streak=0
        for num in nums_set:
            if num-1 not in nums_set: # 说明是序列的起点：
                next=num+1
                current_streak=1
                while next in nums_set: # 集合也可以用和字典相同的方法来查，是否存在某元素
                    current_streak+=1
                    next+=1
                longest_streak=max(longest_streak,current_streak)
        return longest_streak

    def test(self):
        nums=[5,2,1,4,3]
        print(self.solution(nums))

if __name__=='__main__':
    LongestConsecutive().test()

